package com.sparsearr.datastructures.ztr.sort;

import org.apache.logging.log4j.LogManager;
import org.apache.logging.log4j.Logger;

import java.text.SimpleDateFormat;
import java.util.Arrays;
import java.util.Date;

/**
 * @Author: ZhaoTR
 * @Date: Created in 2025/5/29 21:07
 * @Description: 归并排序
 * @Version: 1.0
 */

public class MergeSort {
    private static final Logger logger = LogManager.getLogger(MergeSort.class);

    static int count = 0;

    public static void main(String[] args) {
//        int[] arr = {8, 4, 5, 7, 1, 3, 6, 2};
        int[] arr = new int[80000];
        for (int i = 0; i < 80000; i++) {
            arr[i] = (int) (Math.random() * 8000000);
        }
        int[] temp = new int[arr.length];

        Date date = new Date();
        SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
        String dateStr = simpleDateFormat.format(date);
        System.out.println("排序钱的时间是：" + dateStr);

        mergeSort(arr, 0, arr.length - 1, temp);
//        logger.info("归墟排列之后的数组是{}", Arrays.toString(arr));
//        System.out.println(count);

        Date date1 = new Date();
        String dateStr1 = simpleDateFormat.format(date1);
        System.out.println("排序钱的时间是：" + dateStr1);
    }

    // 递归分解
    public static void mergeSort(int[] arr, int left, int right, int[] temp) {
        if (left < right) {
            int mid = (left + right) / 2;
            // 向左递归，分解
            mergeSort(arr, left, mid, temp);
            // 向右递归，分解
            mergeSort(arr, mid + 1, right, temp);
            // 到合并
            merge(arr, left, mid, right, temp);
        }
    }


    /**
     * 合并方法
     *
     * @param arr   待排序数组
     * @param left  左边的索引
     * @param mid   中间的索引
     * @param right 右边的索引
     * @param temp  临时数组
     */
    public static void merge(int[] arr, int left, int mid, int right, int[] temp) {
        count++;
        // 初始化i，左边的有序索引初始
        int i = left;
        // 初始化j，右边的有序索引初始
        int j = mid + 1;
        // 指向temp当前的索引
        int t = 0;

        // step1 先把左右两边的数据按照规则填充到temp数组
        // 直到左右两边的元素填充完毕
        while (i <= mid && j <= right) {
            // 如果左边的有序序列的元素，小于等于右边的有序序列的元素
            // 则把左边的元素填充到arr
            // t 往后移动，i 往后移动
            if (arr[i] <= arr[j]) {
                temp[t] = arr[i];
                t += 1;
                i += 1;
            } else {
                // 如果右边的有序序列的元素，小于等于左边的有序序列的元素
                // 则把右边的元素填充到arr
                // t 往后移动，j 往后移动
                temp[t] = arr[j];
                t += 1;
                j += 1;
            }
        }

        // step2 把剩余数据的一边的数据填充到temp
        while (i <= mid) {
            // 左边的有序序列还有剩余的元素，就全部填充到arr
            temp[t] = arr[i];
            t += 1;
            i += 1;
        }
        while (j <= right) {
            //  右边的序列还有剩余的元素，就全部填充到arr
            temp[t] = arr[j];
            t += 1;
            j += 1;
        }

        // step3 将temp数组的元素拷贝到arr
        // 注意：并不是每次都拷贝所有
        t = 0;
        // 第一次合并时：tempLeft = 0, right = 1， tempRight = 2, right = 3
        // tempLeft = 0, right = 7
        int tempLeft = left;
        while (tempLeft <= right) {
            arr[tempLeft] = temp[t];
            t += 1;
            tempLeft += 1;
        }

    }
}
